package main

import (
	"fmt"
	"strings"
)

// 环形链表
type CircularLinkedList struct {
	head *Node
}

// 追加元素
func (list *CircularLinkedList) Append(e interface{}) {

	// 创建待追加的node节点
	node := &Node{
		e:    e,
		next: nil,
	}

	// 链表为空
	if list.head.next == nil {
		list.head = node
		list.head.next = list.head
	} else {
		// 迭代找到尾部元素
		tmp := list.head
		for {
			// 当tmp元素的next是head时表示它是尾部元素
			if tmp.next == list.head {
				break
			}
			tmp = tmp.next
		}
		tmp.next = node
		node.next = list.head
	}
}

// 删除元素
func (list *CircularLinkedList) remove(
	e interface{},
	comparator func(e1 interface{}, e2 interface{}) int) (r interface{}) {

	if list.head.next == nil {
		return nil
	}

	tmp := list.head.next
	helper := list.head

	for {
		if comparator(tmp.e, e) == 0 {
			break
		}
		if tmp == list.head {
			return nil
		}
		tmp = tmp.next
		helper = helper.next
	}

	if tmp == list.head {
		if tmp.next == tmp {
			list.head = tmp.next
			tmp.next = nil
		} else {
			helper.next = tmp.next
			list.head = tmp.next
		}
	} else {
		helper.next = tmp.next
	}

	return tmp.e
}

// 打印
func (list *CircularLinkedList) Print() {
	fmt.Println(list.String())
}

// 覆盖String方法，格式化输出
func (list CircularLinkedList) String() string {
	next := list.head.next
	// 空链表
	if next == nil {
		return "[]"
	} else {
		s := "["
		tmp := list.head
		for {
			s += fmt.Sprintf("%v, ", tmp.e)
			if tmp.next == list.head {
				break
			}
			tmp = tmp.next
		}
		return strings.TrimRight(strings.TrimSpace(s), ",") + "]"
	}
}

// 表示一个链表节点
type Node struct {
	e    interface{}
	next *Node
}

// 示例元素结构体
type Student struct {
	id       int
	name     string
	nickname string
}

// 覆盖String方法，格式化输出
func (student *Student) String() string {
	return fmt.Sprintf("{id=%d, name=%s, nickname=%s}", student.id, student.name, student.nickname)
}

func main() {

	var f = func(e1 interface{}, e2 interface{}) int {
		return e1.(*Student).id - e2.(*Student).id
	}

	node := &Node{}

	list := CircularLinkedList{node}

	fmt.Println("list =", list)

	list.Print()

	// 移除
	r := list.remove(&Student{id: 16}, f)
	fmt.Printf("移除的元素是: %v\n", r)

	// 创建元素
	s1 := &Student{1, "宋江", "及时雨"}
	s2 := &Student{2, "卢俊义", "玉麒麟"}
	s3 := &Student{3, "吴用", "智多星"}

	// 追加
	list.Append(s1)
	list.Print()
	list.Append(s2)
	list.Print()
	list.Append(s3)
	list.Print()

	// 打印链表
	fmt.Println(list)

	// 移除
	r = list.remove(&Student{id: 16}, f)
	fmt.Printf("移除的元素是: %v\n", r)
	r = list.remove(&Student{id: 2}, f)
	fmt.Printf("移除的元素是: %v\n", r)
	r = list.remove(&Student{id: 1}, f)
	fmt.Printf("移除的元素是: %v\n", r)
	r = list.remove(&Student{id: 3}, f)
	fmt.Printf("移除的元素是: %v\n", r)

	// 打印链表
	fmt.Println(list)

	// 重新追加
	list.Append(s1)
	fmt.Println(list)
	list.Append(s2)
	fmt.Println(list)
	list.Append(s3)
	fmt.Println(list)
}
